home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / parser.cq / parser.c
Encoding:
C/C++ Source or Header  |  1985-06-03  |  18.0 KB  |  572 lines
  1. #ifdef IGNORE_THIS
  2.  
  3. /*
  4.  
  5. NOTE:    lower down in this program description section, i have examples
  6.     of C code with embedded comments.  this "#ifdef" is here because
  7.     without it, the C compiler treats the end-of-comment delimiters
  8.     (asterisk-slash) as significant, and my examples start generating
  9.     code and errors.  the "#ifdef" causes this whole section to be
  10.     ignored, including the end-of-comment delimiters.
  11.  
  12.  
  13.     PARSER.C    Lloyd Zusman, Master Byte Software, Trump User Group
  14.             (408) 395-5693 (voice only)
  15.  
  16.     This program is a generalized, finite state token parser.  It's
  17.     it is the most powerful parser I've seen on any BBS (if I do say
  18.     so myself).  It allows you extract tokens one at a time from a
  19.     string of characters.  The characters used for white space, for
  20.     break characters, and for quotes can be specified.  Also,
  21.     characters in the string can be preceded by a specifiable escape
  22.     character which removes any special meaning the character may have.
  23.  
  24.     There are a lot of formal parameters in this subroutine call, but
  25.     once you get familiar with them, this routine is fairly easy to use.
  26.     "#define" macros can be used to generate simpler looking calls for
  27.     commonly used applications of this routine.
  28.  
  29.     First, some terminology:
  30.  
  31.     token            used here, a single unit of information in
  32.                 the form of a group of characters.
  33.  
  34.     white space        space that gets ignored (except within quotes
  35.                 or when escaped), like blanks and tabs.  in
  36.                 addition, white space terminates a non-quoted
  37.                 token.
  38.  
  39.     break character        a character that separates non-quoted tokens.
  40.                 commas are a common break character.  the
  41.                 usage of break characters to signal the end
  42.                 of a token is the same as that of white space,
  43.                 except multiple break characters with nothing
  44.                 or only white space between generate a null
  45.                 token for each two break characters together.
  46.  
  47.                 for example, if blank is set to be the white 
  48.                 space and comma is set to be the break
  49.                 character, the line ...
  50.  
  51.                 A, B, C ,  , DEF
  52.  
  53.                 ... consists of 5 tokens:
  54.  
  55.                 1)    "A"
  56.                 2)    "B"
  57.                 3)    "C"
  58.                 4)    ""    (the null string)
  59.                 5)    "DEF"
  60.  
  61.     quote character        a character that, when surrounding a group
  62.                 of other characters, causes the group of
  63.                 characters to be treated as a single token,
  64.                 no matter how many white spaces or break
  65.                 characters exist in the group.  also, a
  66.                 token always terminates after the closing
  67.                 quote.  for example, if ' is the quote
  68.                 character, blank is white space, and comma
  69.                 is the break character, the following
  70.                 string ...
  71.  
  72.                 A, ' B, CD'EF GHI
  73.  
  74.                 ... consists of 4 tokens:
  75.  
  76.                 1)    "A"
  77.                 2)    " B, CD" (note the blanks & comma)
  78.                 3)    "EF"
  79.                 4)    "GHI"
  80.  
  81.                 the quote characters themselves do
  82.                 not appear in the resultant tokens.  the
  83.                 double quotes are delimiters i use here for
  84.                 documentation purposes only.
  85.  
  86.     escape character    a character which itself is ignored but
  87.                 which causes the next character to be
  88.                 used as is.  ^ and \ are often used as
  89.                 escape characters.  an escape in the last
  90.                 position of the string gets treated as a
  91.                 "normal" (i.e., non-quote, non-white, 
  92.                 non-break, and non-escape) character.
  93.                 for example, assume white space, break
  94.                 character, and quote are the same as in the
  95.                 above examples, and further, assume that
  96.                 ^ is the escape character.  then, in the
  97.                 string ...
  98.  
  99.                 ABC, ' DEF ^' GH' I ^ J K^ L ^
  100.  
  101.                 ... there are 7 tokens:
  102.  
  103.                 1)    "ABC"
  104.                 2)    " DEF ' GH"
  105.                 3)    "I"
  106.                 4)    " "    (a lone blank)
  107.                 5)    "J"
  108.                 6)    "K L"
  109.                 7)    "^"    (passed as is at end of line)
  110.  
  111.  
  112.     OK, now that you have this background, here's how to call "parser":
  113.  
  114.     result=parser(flag,token,maxtok,string,white,break,quote,escape,
  115.               brkused,next,quoted)
  116.  
  117.     result:        0 if we haven't reached EOS (end of string), and
  118.             1 if we have (this is an "int").
  119.  
  120.     flag:        right now, only the low order 3 bits are used.
  121.             1 => convert non-quoted tokens to upper case
  122.             2 => convert non-quoted tokens to lower case
  123.             0 => do not convert non-quoted tokens
  124.             (this is a "char").
  125.  
  126.     token:        a character string containing the returned next token
  127.             (this is a "char[]").
  128.  
  129.     maxtok:        the maximum size of "token".  characters beyond
  130.             "maxtok" are truncated (this is an "int").
  131.  
  132.     string:        the string to be parsed (this is a "char[]").
  133.  
  134.     white:        a string of the valid white spaces.  example:
  135.  
  136.             char whitesp[]={" \t"};
  137.  
  138.             blank and tab will be valid white space (this is
  139.             a "char[]").
  140.  
  141.     break:        a string of the valid break characters.  example:
  142.  
  143.             char breakch[]={";,"};
  144.  
  145.             semicolon and comma will be valid break characters
  146.             (this is a "char[]").
  147.             
  148.             IMPORTANT:  do not use the name "break" as a C
  149.             variable, as this is a reserved word in C.
  150.  
  151.     quote:        a string of the valid quote characters.  an example
  152.             would be
  153.  
  154.             char whitesp[]={"'\"");
  155.  
  156.             (this causes single and double quotes to be valid)
  157.             note that a token starting with one of these characters
  158.             needs the same quote character to terminate it.
  159.  
  160.             for example, 
  161.  
  162.             "ABC '
  163.             
  164.             is unterminated, but
  165.  
  166.             "DEF" and 'GHI'
  167.  
  168.             are properly terminated.  note that different quote
  169.             characters can appear on the same line; only for
  170.             a given token do the quote characters have to be
  171.             the same (this is a "char[]").
  172.  
  173.     escape:        the escape character (NOT a string ... only one
  174.             allowed).  use zero if none is desired (this is
  175.             a "char").
  176.  
  177.     brkused:    the break character used to terminate the current
  178.             token.  if the token was quoted, this will be the
  179.             quote used.  if the token is the last one on the
  180.             line, this will be zero (this is a pointer to a
  181.             "char").
  182.  
  183.     next:        this variable points to the first character of the
  184.             next token.  it gets reset by "parser" as it steps
  185.             through the string.  set it to 0 upon initialization,
  186.             and leave it alone after that.  you can change it
  187.             if you want to jump around in the string or re-parse
  188.             from the beginning, but be careful (this is a
  189.             pointer to an "int").
  190.  
  191.     quoted:        set to 1 (true) if the token was quoted and 0 (false)
  192.             if not.  you may need this information (for example:
  193.             in C, a string with quotes around it is a character
  194.             string, while one without is an identifier).
  195.  
  196.             (this is a pointer to a "char").
  197.  
  198.     Example 1:
  199.  
  200.     char *whitesp[]={" \t");    /* blank and tab */
  201.     char *breakch[]={",\r");    /* comma and carriage return */
  202.     char *quotech[]={"'\""};    /* single and double quote */
  203.     char escape='^';        /* "uparrow" is escape */
  204.  
  205.     main()
  206.     {
  207.       char *fgets(),line[81],brkused,quoted,token[81];
  208.       int i,next;
  209.  
  210.       while(fgets(line,80,stdin)!=NULL)    /* get line */
  211.       {
  212.  
  213.         printf("Line: %s",line);        /* already has <CR> */
  214.         i=0;
  215.  
  216.         next=0;                /* make sure you do this */
  217.  
  218.         while(parser(2,token,80,line,whitesp,breakch,quotech,escape,
  219.              &brkused,&next,"ed)==0)
  220.         {
  221.           printf(" Token %d = (%s)\n",++i,token);
  222.  
  223.           if(brkchar=='\r')    /* <CR> is a break so it won't be included  */
  224.         break;        /* in the token.  treat as end-of-line here */
  225.         }
  226.       }
  227.     }
  228.  
  229.  
  230.  
  231.     In the above example, lines are read from stdin and broken up into
  232.     tokens.  All non-quoted tokens are converted to lower case.  Since
  233.     fgets() returns the final carriage return, we treat it as a break
  234.     character to keep it out of the returned token.  Also, since the only
  235.     way "parser" will return a non-zero error code is at end of line,
  236.     we test "brkchar" to see if we've gotten to the final carriage
  237.     return, and we explicitly break out of the inner loop if we've
  238.     hit it.  Note that since fgets() puts the final <CR> right before
  239.     the end-of-string, if we left out the "if(brkchar='\r')" test,
  240.     we'd get one extra null token (just as if the line ended with a
  241.     single comma).  Run this example to see how it all works.
  242.  
  243.     Example 2:
  244.  
  245.         .
  246.         .
  247.         .
  248.  
  249.     next=0;
  250.     result=parser(1, newstr, 80, str, "", "", "", 0, &brkused, &next,
  251.               "ed);
  252.         .
  253.         .
  254.         .
  255.     
  256.     this call takes whatever is in "str" and converts it to upper case,
  257.     putting the result in "newstr".
  258.  
  259.     *** end of examples ***
  260.  
  261.     in case you're interested, "parser.c" was inspired by a system
  262.     subroutine that comes as part of the PRIMOS operating system for
  263.     the Prime Computer:  "gt$par.plp".  i loosely patterned this routine
  264.     after the Prime routine.
  265.  
  266.     Revisions:
  267.  
  268.     09/30/84    Lloyd Zusman    Initial coding
  269.  
  270.  
  271. NOTE:    This program was developed to run on the "Trump Card" (a Z8000
  272.     CPU on a board specially adapted for plugging into an IBM PC).
  273.     The C compiler I used is fairly standard, and I assume this
  274.     program will compile pretty much "as is" on either the Lattice
  275.     C compiler or the Computer Innovations C compiler.  Any 
  276.     incompatibilities between the Trump C compiler and these other
  277.     compilers should be minimal.
  278.  
  279.     Since the C compiler I used generates 32-bit pointers, you may
  280.     feel the urge to use the large model for Lattice or Computer
  281.     Innovations.  However, I don't think I do anything in this
  282.     program that depends on the pointers being any given size, so
  283.     you should be able to compile it using any "size" model you see
  284.     fit.
  285.  
  286.     Incidentally, this "Trump Card" I mentioned is something I'm
  287.     really happy with.  It has a 10 MHz Z8000 and up to 512K of
  288.     memory.  The memory is standard "4164"-type dynamic RAM, and
  289.     therefore the computer doesn't quite run at 10 MHz all the
  290.     time.  The fastest "4164" RAM I've been able to find is 120
  291.     nanosecond memory, but I'm pushing my "Trump Card" up to
  292.     9 MHz and it works just fine with these chips.
  293.  
  294.     There is a simple operating system that comes with this "Trump
  295.     Card", and you can go back and forth between it and your PC.
  296.     As of now (mid October, 1984), the Trump Card's operating system
  297.     doesn't quite support concurrent processes going simultaneously
  298.     on buth CPU's, but that capability should come out fairly soon.
  299.  
  300.     Other nice things that come with this card are:
  301.  
  302.         A Z80 emulator that lets you run CPM programs.
  303.         
  304.         A C compiler (mentioned above).  A 600+ line C program
  305.         that took 6.5 minutes to compile and link on the PC
  306.         (Computer Innovations C compiler, IBM PC standard
  307.         linker) took exactly 22 seconds to compile and link
  308.         on the Trump Card.  You could test and develop a C program
  309.         on the Trump Card, taking advantage of the speed, and then
  310.         move it over to the PC for one last re-compile when
  311.         you're ready to put it into production.  So far, the
  312.         only differences I could find between the Trump's C
  313.         compiler and Computer Innovations are (1) slight 
  314.         differences in the format string in "printf" (these
  315.         normally won't even show up); (2) "register" data
  316.         types really get assigned to registers on the Trump
  317.         C compiler; (3) in-line machine language is allowed
  318.         in the Trump C compiler.
  319.  
  320.         A BASIC system that will run IBM's Basic programs
  321.         with very few changes, but quite a bit faster.
  322.  
  323.         A compiler for a language called "Y".  This is
  324.         a "multi-level language", which at it's lowest
  325.         level is just a Z8000 assembler, at the next highest
  326.         level lets you use C-like and Pascal-like constructs
  327.         in your assembly code, and at it's highest level is
  328.         a Meta-Compiler (like YACC, for example) which lets
  329.         you use Backus-Naur grammer constructs to define your
  330.         own high level languages. 
  331.  
  332.         Software to make all or part of Trump memory look
  333.         like a ramdisk and/or a print spooler for your PC.
  334.  
  335.         Function calls (analogous to interrupt 021h in MS-DOS)
  336.         which let you do lots of things from applications
  337.         programs on the Trump card, including the ability to
  338.         initiate interrupts on the 8088.
  339.  
  340.         Other various and sundry things like an editor, a linker,
  341.         etc.
  342.  
  343.     Using this Trump Card has really brought home to me how far away
  344.     from "state of the art" these IBM PC's (and XT's and even AT's)
  345.     are.  IBM used slow, substandard technology in it's PC's, XT's,
  346.     and even AT's.  The 6.5-minute C compile and link that took 22
  347.     seconds on the Trump Card illustrates this point.  If you assume
  348.     that the Computer Innovations C compiler I used on the PC is twice
  349.     as slow as it could be (a fairly safe assumption:  Lattice runs
  350.     quite a bit faster), factoring that in still leaves an approximately
  351.     8-to-1 time differential that can only be accounted for by hardware
  352.     inefficiencies in the PC (the badly designed Intel 8088 chip, the
  353.     slow 4.7 MHz clock rate, etc.).  We can't even attribute this slowness
  354.     to the hard disk IBM uses (there are cheap, reliable, commercially
  355.     available internal 10 MB hard disks that are 3 times faster than
  356.     the ones IBM uses) nor to its bus, since the Trump Card uses the
  357.     same disk and the same bus.  Nor can we attribute it to the fact
  358.     that the Trump Card has 512 K of memory, since I have an AST
  359.     "Six Pack Plus" on my PC which has 384 K on it, so my total memory
  360.     on the PC side of things is 640 K.  If you have one of those new
  361.     AT's, you're still only running 3 times faster than the PC (this is
  362.     IBM's claim ... I'll bet you that in most real applications, it's not
  363.     even that fast), so the Trump card is still more than twice as fast
  364.     as the AT can ever hope to be.  What this all boils down to is that
  365.     it's necessary to soup up these PC's in order to make them capable
  366.     of doing anything useful in a reasonable period of time.  The Trump
  367.     Card is one of probably many good ways to turn your IBM PC into
  368.     a real computer.
  369.  
  370.     There was a writeup on the Trump Card in two consecutive recent
  371.     "Byte" issues (May and June, 1984, I believe).  If you're interested
  372.     in more information, you can contact me at the phone number above,
  373.     or you can dial into the official Trump BBS at (408) 923-5565 and
  374.     look around or leave a message for the Sysop.
  375.  
  376.     -Lloyd Zusman, Master Byte Software
  377.  
  378.  
  379. #endif        /* goes with initial "#ifdef" */
  380.  
  381. /* states */
  382.  
  383. #define IN_WHITE 0
  384. #define IN_TOKEN 1
  385. #define IN_QUOTE 2
  386. #define IN_OZONE 3
  387.  
  388. int _p_state;      /* current state      */
  389. unsigned _p_flag;  /* option flag        */
  390. char _p_curquote;  /* current quote char */
  391. int _p_tokpos;     /* current token pos  */
  392.  
  393. /* routine to find character in string ... used only by "parser" */
  394.  
  395. sindex(ch,string)
  396. char ch,*string;
  397.  
  398. {
  399.   char *cp;
  400.   for(cp=string;*cp;++cp)
  401.     if(ch==*cp)
  402.       return (int)(cp-string);  /* return postion of character */
  403.   return -1;                    /* eol ... no match found */
  404. }
  405.     
  406. /* routine to store a character in a string ... used only by "parser" */
  407.  
  408. chstore(string,max,ch)
  409. char *string,ch;
  410. int max;
  411.  
  412. {
  413.   char c;
  414.   if(_p_tokpos>=0&&_p_tokpos<max-1)
  415.   {
  416.     if(_p_state==IN_QUOTE)
  417.       c=ch;
  418.     else
  419.       switch(_p_flag&3)
  420.       {
  421.         case 1:             /* convert to upper */
  422.           c=toupper(ch);
  423.           break;
  424.   
  425.         case 2:             /* convert to lower */
  426.           c=tolower(ch);
  427.           break;
  428.       
  429.         default:            /* use as is */
  430.           c=ch;
  431.           break;
  432.       }
  433.     string[_p_tokpos++]=c;
  434.   }
  435.   return;
  436. }
  437.   
  438. /* here it is! */
  439.  
  440. parser(inflag,token,tokmax,line,white,brkchar,quote,eschar,brkused,next,quoted)
  441. unsigned inflag;
  442. char *token,*line,*white,*brkchar,*quote,*brkused,*quoted,eschar;
  443. int tokmax,*next;
  444.  
  445. {
  446.   int qp;
  447.   char c,nc;
  448.           
  449.   *brkused=0;           /* initialize to null */      
  450.   *quoted=0;        /* assume not quoted  */
  451.  
  452.   if(!line[*next])      /* if we're at end of line, indicate such */
  453.     return 1;
  454.  
  455.   _p_state=IN_WHITE;       /* initialize state */
  456.   _p_curquote=0;           /* initialize previous quote char */
  457.   _p_flag=inflag;          /* set option flag */
  458.  
  459.   for(_p_tokpos=0;c=line[*next];++(*next))      /* main loop */
  460.   {
  461.     if((qp=sindex(c,brkchar))>=0)  /* break */
  462.     {
  463.       switch(_p_state)
  464.       {
  465.         case IN_WHITE:          /* these are the same here ...    */
  466.         case IN_TOKEN:          /* ... just get out        */
  467.     case IN_OZONE:        /* ditto            */
  468.           ++(*next);
  469.           *brkused=brkchar[qp];
  470.           goto byebye;
  471.         
  472.         case IN_QUOTE:           /* just keep going */
  473.           chstore(token,tokmax,c);
  474.           break;
  475.       }
  476.     }
  477.     else if((qp=sindex(c,quote))>=0)  /* quote */
  478.     {
  479.       switch(_p_state)
  480.       {
  481.         case IN_WHITE:   /* these are identical, */
  482.           _p_state=IN_QUOTE;        /* change states   */
  483.           _p_curquote=quote[qp];         /* save quote char */
  484.           *quoted=1;    /* set to true as long as something is in quotes */
  485.           break;
  486.   
  487.         case IN_QUOTE:
  488.           if(quote[qp]==_p_curquote)    /* same as the beginning quote? */
  489.       {
  490.             _p_state=IN_OZONE;
  491.         _p_curquote=0;
  492.       }
  493.           else
  494.             chstore(token,tokmax,c);    /* treat as regular char */
  495.           break;
  496.  
  497.     case IN_TOKEN:
  498.     case IN_OZONE:
  499.       *brkused=c;            /* uses quote as break char */
  500.       goto byebye;
  501.       }
  502.     }
  503.     else if((qp=sindex(c,white))>=0)       /* white */
  504.     {
  505.       switch(_p_state)
  506.       {
  507.         case IN_WHITE:
  508.     case IN_OZONE:
  509.           break;        /* keep going */
  510.           
  511.         case IN_TOKEN:
  512.           _p_state=IN_OZONE;
  513.           break;
  514.           
  515.         case IN_QUOTE:
  516.           chstore(token,tokmax,c);     /* it's valid here */
  517.           break;
  518.       }
  519.     }
  520.     else if(c==eschar)            /* escape */
  521.     {
  522.       nc=line[(*next)+1];
  523.       if(nc==0)            /* end of line */
  524.       {
  525.     *brkused=0;
  526.     chstore(token,tokmax,c);
  527.     ++(*next);
  528.     goto byebye;
  529.       }
  530.       switch(_p_state)
  531.       {
  532.     case IN_WHITE:
  533.       --(*next);
  534.       _p_state=IN_TOKEN;
  535.       break;
  536.  
  537.     case IN_TOKEN:
  538.     case IN_QUOTE:
  539.       ++(*next);
  540.       chstore(token,tokmax,nc);
  541.       break;
  542.  
  543.     case IN_OZONE:
  544.       goto byebye;
  545.       }
  546.     }
  547.     else        /* anything else is just a real character */
  548.     {
  549.       switch(_p_state)
  550.       {
  551.         case IN_WHITE:
  552.           _p_state=IN_TOKEN;        /* switch states */
  553.           
  554.         case IN_TOKEN:           /* these 2 are     */
  555.         case IN_QUOTE:           /*  identical here */
  556.           chstore(token,tokmax,c);
  557.           break;
  558.  
  559.     case IN_OZONE:
  560.       goto byebye;
  561.       }
  562.     }
  563.   }             /* end of main loop */
  564.  
  565. byebye:
  566.   token[_p_tokpos]=0;   /* make sure token ends with EOS */
  567.   
  568.   return 0;
  569.   
  570. }
  571.  
  572.